package main

import (
	"sort"
)

func main() {

	nums := []int{-1, 2, 1, -4}
	target := 1
	println(threeSumClosest(nums, target))
}

/*
	三数之和

解法：
	先排序计算
	取前面三个数，如果不等，将指针移动
*/
func threeSumClosest(nums []int, target int) int {
	if len(nums) <= 3 {
		return sliceIntSum(nums)
	}

	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})

	//设置指针
	point := 0
	start := target - sliceIntSum(nums[point:point+3])

	for point+3 < len(nums) {

		point++
		end := target - sliceIntSum(nums[point:point+3])
		if start < 0 {
			if end > start {
				start = end
			} else {
				break
			}
		} else {
			if end < start {
				start = end
			} else {
				break
			}
		}

	}

	return ^start + 1 + target
}

//切片求和
func sliceIntSum(arr []int) (sum int) {
	for _, v := range arr {
		sum += v
	}
	return
}

/**
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。
*/

var letterCombinationMap = map[string][]string{
	"2": []string{"a", "b", "c"},
	"3": []string{"d", "e", "f"},
	"4": []string{"g", "h", "i"},
	"5": []string{"j", "k", "l"},
	"6": []string{"m", "n", "o"},
	"7": []string{"p", "q", "r", "s"},
	"8": []string{"t", "u", "v"},
	"9": []string{"w", "x", "y", "z"},
}

func letterCombinations(digits string) []string {

	for _, _ = range digits {

	}

	return nil
}

type ListNode struct {
	Val  int
	Next *ListNode
}

/*
	合并两个有序链表
*/
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil && l2 == nil {
		return nil
	}
	if l1 == nil && l2 != nil {
		return l2
	}
	if l1 != nil && l2 == nil {
		return l1
	}

	newNode := l1

	for l2 != nil {
		//判断是否大于l1,如果大于，则移动
		if l2.Val < l1.Val {
			//创建一个新node
			nw := &ListNode{Val: l1.Val, Next: l1.Next}
			l1.Val = l2.Val
			l1.Next = nw

			l2 = l2.Next
			if l2 == nil {
				break
			}
		}

		if l1.Next != nil {
			l1 = l1.Next
		} else {
			l1.Next = l2
			break
		}
	}

	return newNode
}
